// https://www.acwing.com/problem/content/3/

#include <iostream>
#include <vector>

using namespace std;

/**
 * 解决完全背包问题（每个物品可重复选择）
 * @param w 背包的最大容量
 * @param weights 物品的重量数组
 * @param values 物品的价值数组
 * @return 返回一个整数，即在容量不超过 w 的情况下，能获得的最大价值
 */
int knapsack(const int w, const vector<int> &weights, const vector<int> &values) {
    // 物品数量
    const auto n = weights.size();
    // dp[k] 表示当最大容量为 k 时，背包能装物品的最大价值
    vector<int> dp(w + 1);
    // 初始化边界，当背包容量为 0 时，背包能装物品的最大价值为 0
    dp[0] = 0;
    // 遍历每个物品，i 表示当前处理的物品索引
    for (int i = 0; i < n; i++) {
        // 从 weights[i]（当前物品的重量）开始，正序遍历到 w，表示当前的背包容量 j
        // 正序遍历在完全背包问题中至关重要，因为每个物品可以选择多次。
        // 正序保证每次选择时，dp[j] 已包括前一次选择该物品的情况
        for (int j = weights[i]; j <= w; j++) {
            // 更新 dp[j] 的值，以决定是否放入当前物品 i
            // 如果不放入当前物品，dp[j] 保持原值 dp[j]
            // 如果放入当前物品，得到的总价值为 values[i] + dp[j - weights[i]]（当前物品价值加上容量减去物品重量后的剩余容量下的最大价值）
            // max 函数选择两者中的较大值，以确保 dp[j] 存储的是容量为 j 时可以获得的最大价值
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[w];
}

int main() {
    int n, w;
    cin>>n>>w;
    vector<int> weights(n), values(n);

    for (int i = 0; i < n; i++) {
        cin>>weights[i]>>values[i];
    }
    cout<<knapsack(w, weights, values)<<endl;
    return 0;
}

/*
4 5
1 2
2 4
3 4
4 5

10
*/